Bose-Chaudhuri-Hocquenghem (BCH) code is one of the most widely used error correction code (ECC) techniques in the storage and communication devices. BCH code can detect and correct random errors occurred due to channel noises and defects within memory devices. The encoding procedures of BCH code word can be implemented by linear feedback shift register (LFSR) and some combination logics together. Comparing with encoding procedures of the BCH code words, decoding procedures of the BCH code words are much complicated as shown in FIG. 1. Decoding procedures are as below: After receiving a code word (S01), in order to decode it, one should compute a syndrome according to specified polynomials (S02). Then, depending on the syndrome, an error-location polynomial can be found (S03). Next, by calculating the roots of the error-location polynomial, error-location numbers can be obtained (S04). Finally, an erroneous code word can be corrected by above steps (S05).
Conventionally, Peterson-Gorenstein-Zierler (PGZ) algorithm or Berlekamp-Massey (BM) algorithm can be used to find out the aforementioned error-location polynomial. Since the complexity of the PGZ algorithm is higher than the BM algorithm and the BM algorithm can process decoding with faster speed, the BM algorithm is more popular in hardware implementation. However, due to the multiplication inverse used in the BM algorithm, complexity of hardware of the circuit increases significantly.
According to the error-location polynomial λ(x)=λ0+λ1x+ . . . +λtxt, the roots of λ(x) can be found simply by substituting 1, α, α2, . . . , αn-1 (n=2m−1) into λ(x). Since αn=1, α−1=αn-1. Therefore, if α1 is an error-location number, αn-1 is another error-location number. Conventionally, this substitution procedure can be operated iteratively by Chien's search. However, this sequential circuit only can find one error location number per clock. In order to improve the throughput of BCH decoding per clock, parallel computation architecture can be applied in the step of Chien's search as shown in FIG. 2. Therefore, p error locations can be found in one clock.
Let λ1x+ . . . +λtxt in the error location polynomial λ(x) to be Y(x). If αi is a root of λ(x), we can have Y(αi)=1. Under an architecture of p parallel computations, Y(αup+i) can be reformed as:
      Y    ⁡          (              α                  up          +          i                    )        =                    ∑                  j          =          1                t            ⁢                        λ          j                ⁢                  α          upj                ⁢                  α          ij                      =                  ∑                  j          =          1                t            ⁢                        ω          j                ⁢                  α          ij                    Due to parallelization, the number of iterative operations becomes [n/p]. Numeral u represents the number of iterative operations currently and ωj is an updated value in each iterative operations, where 1≦i≦p and 1≦j≦t. When the order in Galois field in 2m, there are pt finite field multipliers, p t-input m-bit finite field adders, t m-bit registers and t m-bit multiplexers in the parallel computation architecture in FIG. 2.
If ωjαij in the above function is expressed as a matrix, we can have
                                                                                          ω                  j                                ⁢                                  α                  ij                                            =                            ⁢                                                (                                                            ω                                              j                        ⁢                                                                                                  ⁢                        0                                                              +                                                                  ω                                                  j                          ⁢                                                                                                          ⁢                          1                                                                    ⁢                      α                                        +                    …                    +                                                                  ω                                                  j                          ,                                                      m                            -                            1                                                                                              ⁢                                              α                                                  m                          -                          1                                                                                                      )                                ⁢                                  α                  ij                                                                                                        =                            ⁢                              (                                                                            ω                                              j                        ⁢                                                                                                  ⁢                        0                                                              ⁢                                          α                      ij                                                        +                                                            ω                                              j                        ⁢                                                                                                  ⁢                        1                                                              ⁢                                          α                                              ij                        +                        1                                                                              +                  …                  +                                                            ω                                              j                        ,                                                  m                          -                          1                                                                                      ⁢                                          α                                              ij                        +                        m                        -                        1                                                                                            )                                                                                        =                            ⁢                                                [                                                                                                              ω                                                      j                            ⁢                                                                                                                  ⁢                            0                                                                                                                                                ω                                                      j                            ⁢                                                                                                                  ⁢                            1                                                                                                                      …                                                                                              ω                                                      j                            ,                                                          m                              -                              1                                                                                                                                                            ]                                ⁢                                                                  ×                                                        ⁢                          ⁢                          [                                                  α              0              ij                                                          α              1              ij                                            …                                              α                              m                -                1                            ij                                                                          α              0                              ij                +                1                                                                        α              1                              ij                +                1                                                          …                                              α                              m                -                1                                            ij                +                1                                                                          ⋮                                ⋮                                ⋱                                ⋱                                                              α              0                              ij                +                m                -                1                                                                        α              1                              ij                +                m                -                1                                                          …                                              α                              m                -                1                                            ij                +                m                -                1                                                        ]        ⁢                  ⁢                  =                  Ω        j            ⁢              A        ij              ,where Ωj and Aij are a binary m×m matrix and a binary 1×m matrix, respectively. ωjαij represents computed results from a finite field multiplexer the ith row and the jth column. Therefore, Y(αup+i) can be derived from:
      Y    ⁡          (              α                  up          +          i                    )        =                    ∑                  j          =          1                t            ⁢                        Ω          j                ⁢                  A          ij                      =                            [                                                                      Ω                  1                                                                              Ω                  2                                                            …                                                              Ω                  t                                                              ]                ⁡                  [                                                                      A                                      i                    ⁢                                                                                  ⁢                    1                                                                                                                        A                                      i                    ⁢                                                                                  ⁢                    2                                                                                                      ⋮                                                                                      A                                      i                    ⁢                                                                                  ⁢                    t                                                                                ]                    .      Please notice that Y(αup+i) is a 1×m matrix. In order to express all outputs in FIG. 2, there should be a matrix including all outputs, Y(u), in the uth iterative operation. Hence, Y(u) can be shown as below matrix:
                              Y          ⁡                      (            u            )                          =                ⁢                  [                                                                      Y                  ⁡                                      (                                          α                                              up                        +                        1                                                              )                                                                                                Y                  ⁡                                      (                                          α                                              up                        +                        2                                                              )                                                                              …                                                              Y                  ⁡                                      (                                          α                                              up                        +                        p                                                              )                                                                                ]                                        =                ⁢                              [                                                                                Ω                    1                                                                                        Ω                    2                                                                    …                                                                      Ω                    t                                                                        ]                    ⁡                      [                                                                                A                    11                                                                                        A                    21                                                                    …                                                                      A                                          p                      ⁢                                                                                          ⁢                      1                                                                                                                                        A                    12                                                                                        A                    22                                                                    …                                                                      A                                          p                      ⁢                                                                                          ⁢                      2                                                                                                                    ⋮                                                  ⋮                                                  ⋱                                                  ⋮                                                                                                  A                                          1                      ⁢                                                                                          ⁢                      t                                                                                                            A                                          2                      ⁢                                                                                          ⁢                      t                                                                                        …                                                                      A                    pt                                                                        ]                                                            =                    ⁢                                    Ω              ⁡                              (                u                )                                      ⁢            Ay                          ,            where Ω(u) is a 1×mt binary matrix, representing intermediate values of the uth iterative operation, Ay is constant and independent of the iterative operation. It should be noticed that computations of the Chien's search under the architecture of p parallel computations are all formulated in one single matrix from the multiplication of Ω(u) and Ay.
Further, updated values of Ω(u) can be used in the next iterative operations. Thus, Ω(u+1)=[ω1αp ω2α2p . . . ωtαtp] and
      Ω    ⁡          (              u        +        1            )        =                    [                                                            Ω                1                                                                    Ω                2                                                    …                                                      Ω                t                                                    ]            ⁡              [                                                            A                                  1                  ⁢                                                                          ⁢                  p                                                                    0                                      …                                      0                                                          0                                                      A                                  2                  ⁢                                                                          ⁢                  p                                                                    …                                      0                                                          ⋮                                      ⋮                                      ⋱                                      ⋮                                                          0                                      0                                      …                                                      A                tp                                                    ]              =                  Ω        ⁡                  (                      u            +            1                    )                    ⁢              A        Ω            Finally, it is obtained that [Y(u) Ω(u+1)]=Ω(u)[Ay AΩ]. The Chien's search circuit having the architecture of p parallel computations for implementing the aforementioned formula is shown in FIG. 3. The circuit design was disclose in IEEE Transactions on circuits and systems-II: Express Briefs, Vol. 58, No. 8, on August 2011, titled Low Complexity Parallel Chien's Search Structure Using Two-Dimensional Optimization, by Youngjoo Lee et al. The outputted error vectors can be available by processing XOR for the outputs of Y(u) and λ0.
The circuit design mentioned above can only applied to a fixed code rate and coed length over the same GF(2m). For some applications requiring different code rates, coed lengths even different m in GF(2m), it is not applicable. Hence, a new Chien's search circuit is needed to fulfill the above requirement.